Search for: All records

We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$$\mathrm{Quasi}-\mathrm{NP}=\mathrm{NTIME}\left[n^{{\left(\log n\right)}^{O\left(1\right)}}\right]$and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathcal { C}$$C$, by showing that$\mathcal { C}$$C$admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class${\mathcal C}$$C$. Say that a symmetric Boolean functionf(x₁,…,x_n) issparseif it outputs 1 onO(1) values of${\sum }_{i} x_{i}$${\sum }_i{x}_i$. We show that for every sparsef, and for all “typical”$\mathcal { C}$$C$, faster#SAT algorithms for$\mathcal { C}$$C$circuits imply lower bounds against the circuit class$f \circ \mathcal { C}$$f\circ C$, which may bestrongerthan$\mathcal { C}$$C$itself. In particular:

#SAT algorithms forn^k-size$\mathcal { C}$$C$-circuits running in 2ⁿ/n^ktime (for allk) implyNEXPdoes not have$(f \circ \mathcal { C})$$(f\circ C)$-circuits of polynomial size.

Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJ∘ACC⁰∘THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC⁰[Williams JACM’14] andACC⁰∘THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.

We present early spectral observations of the very slow Galactic nova Gaia22alz, over its gradual rise to peak brightness that lasted 180 d. During the first 50 d, when the nova was only 3–4 mag above its normal brightness, the spectra showed narrow (FWHM ≈ 400 km s−1) emission lines of H Balmer, He i, He ii, and C iv but no P Cygni absorption. A few weeks later, the high-excitation He ii and C iv lines disappeared, and P Cygni profiles of Balmer, He i, and eventually Fe ii lines emerged, yielding a spectrum typical of classical novae before peak. We propose that the early (first 50 d) spectra of Gaia22alz, particularly the emission lines with no P Cygni profiles, are produced in the white dwarf’s optically thin envelope or accretion disc, reprocessing ultraviolet and potentially X-ray emission from the white dwarf after a dramatic increase in the rate of thermonuclear reactions, during a phase known as the ‘early X-ray/UV flash’. If true, this would be one of the rare times that the optical signature of the early X-ray/UV flash has been detected. While this phase might last only a few hours in other novae and thus be easily missed, it was possible to detect in Gaia22alz due to its very slow and gradual rise and thanks to the efficiency of new all-sky surveys in detecting transients on their rise. We also consider alternative scenarios that could explain the early spectral features of Gaia22alz and its gradual rise.

Progressive cementation and sealing of fault-localized fractures impact crustal mass transport and the recovery of fault strength following slip events. We use discrete fracture network (DFN) models to examine how fracture sealing during end-member cementation mechanisms (i.e., reaction- versus transported-limited cementation) influences the partitioning of fluid flow through time. DfnWorks was used to generate randomized fracture networks parameterized with fracture orientation data compiled from field studies. Single-phase flow simulations were performed for each network over a series of timesteps, and network parameters were modified to reflect progressive fracture sealing consistent with either reaction- or transport-limited crystal growth. Results show that when fracture cementation is reaction-limited, fluid flow becomes progressively channelized into a smaller number of fractures with larger apertures. When fracture cementation is transport-limited, fluid flow experiences progressive dechannelization, becoming more homogeneously distributed throughout the fracture network. These behaviors are observed regardless of the DFN parameterization, suggesting that the effect is an intrinsic component of all fracture networks subjected to the end-member cementation mechanisms. These results have first-order implications for the spatial distribution of fluid flow in fractured rocks and recovery of permeability and strength during fault/fracture healing in the immediate aftermath of fault slip.